GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Hamming-Code</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Hamming-Code</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Hamming-Code ist ein von <a href="Richard_Hamming" title="Richard Hamming">Richard Wesley Hamming</a> entwickelter <a href="Linearer_Code" title="Linearer Code">linearer</a> <a href="Fehlerkorrekturverfahren" title="Fehlerkorrekturverfahren">fehlerkorrigierender</a> <a href="Blockcode" title="Blockcode">Blockcode</a>, der in der <a href="Digitale_Signalverarbeitung" title="Digitale Signalverarbeitung">digitalen Signalverarbeitung</a> und der <a href="Nachrichtentechnik" title="Nachrichtentechnik">Nachrichtentechnik</a> zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird.

Beim Hamming-Code handelt es sich um eine Klasse von Blockcodes unterschiedlicher Länge, die durch eine allgemeine Bildungsvorschrift gebildet werden. Die Besonderheit dieses Codes besteht in der Verwendung mehrerer <a href="Paritybit" class="mw-redirect" title="Paritybit">Paritätsbits</a>. Diese Bits ergänzen jeweils unterschiedlich gewählte Gruppen von den die Information tragenden Nutzdatenbits. Durch eine geschickte Wahl der Gruppierung, deren mathematische Grundlagen im Folgenden beschrieben sind, ist nicht nur eine Fehlererkennung, sondern auch eine Fehlerkorrektur der übertragenen Datenbits möglich.

Die einzelnen Codewörter des Hamming-Codes weisen einen <a href="Hamming-Abstand" title="Hamming-Abstand">Hamming-Abstand</a> von 3 auf. Durch diesen Unterschied von jeweils drei Bitstellen kann der Decoder einen oder zwei Bitfehler in einem Datenblock erkennen, aber nur einen Bitfehler korrigieren. Bei zwei Bitfehlern liefert der Decoder ein gültiges, aber falsches Codewort. Der erweiterte Hamming-Code mit einem Hamming-Abstand von 4 kann durch ein zusätzliches <a href="Parit%C3%A4tsbit" title="Paritätsbit">Paritätsbit</a> bis zu drei Bitfehler in einem Datenblock erkennen, aber auch nur einen Bitfehler korrigieren. Zwei Bitfehler werden bei dem erweiterten Hamming-Code als fehlerhaftes (ungültiges) Codewort erkannt, das nicht korrigierbar ist.

<th style="background:#FFC0C0" colspan="2">Eigenschaften binärer Hamming-Code

</th></tr>

<tr>

<td>Stellenzahl</td>

<td>2k−1, k ≥ 2 und ganzzahlig

</td></tr>

<tr>

<td>Gewicht</td>

<td>3

</td></tr>

<tr>

<td>Maximaldistanz</td>

<td>3

</td></tr>

<tr>

<td><a href="Hamming-Abstand" title="Hamming-Abstand">Hamming-Abstand</a></td>

<td>3

</td></tr>

<tr>

<td><a href="Redundanz_(Informationstheorie)" title="Redundanz (Informationstheorie)">Redundanz</a></td>

<td>k

</td></tr>

<tr>

<td colspan="2">k ist die Anzahl der <a href="Parit%C3%A4tsbit" title="Paritätsbit">Paritätsbits</a> pro Codewort

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

In den 1940er Jahren arbeitete <a href="Richard_Hamming" title="Richard Hamming">Richard Hamming</a> in der Firma <a href="Bell_Labs" class="mw-redirect" title="Bell Labs">Bell Labs</a> an einem Computer namens Bell Model V, der mit fehleranfälligen elektromechanischen <a href="Relais" title="Relais">Relais</a> mit zwei <a href="Maschinenzyklus" class="mw-redirect" title="Maschinenzyklus">Maschinenzyklen</a> pro Sekunde ausgestattet war. Die zu Dateneingaben verwendeten <a href="Lochkarte" title="Lochkarte">Lochkarten</a> konnten durch Abnutzung bei der Leseoperation Fehler aufweisen, die zu den normalen Bürozeiten durch Angestellte der Bell Labs von Hand korrigiert werden mussten. Zu den üblichen Arbeitszeiten von Richard Hamming, außerhalb der Bürozeiten und am Wochenende, führten diese Lesefehler dazu, dass der Computer die fehlerhaften Lochkarten übersprang und an anderen Lochkarten weiterarbeitete.

Hamming war durch diese Fehler und den mehrfachen Aufwand frustriert und entwickelte in Folge einen speziellen Code, durch den die Maschine Lesefehler von Lochkarten in bestimmtem Umfang selbständig erkennen und korrigieren konnte. Im Jahr 1950 publizierte er diesen Hamming-Code,<a href="#cite_note-1">[1]</a> der noch heute und in teilweise erweiterten Formen im Bereich der <a href="Kanalkodierung" title="Kanalkodierung">Kanalkodierung</a> verbreitete Anwendung findet.

<div class="mw-heading mw-heading2"><h2 id="Aufbau_des_Codes">Aufbau des Codes</h2></div>

Im Folgenden werden nur <a href="Dualsystem" title="Dualsystem">binäre</a> Hamming-Codes dargestellt. Binäre Hamming-Codes basieren auf <a href="Paritybit" class="mw-redirect" title="Paritybit">Paritycodes</a> über einem Datenblock fixer Länge. Der Datenblock, auch als „Datenwort“ oder „Nachrichtenwort“ bezeichnet, umfasst <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bits und enthält die eigentliche Nutzinformation. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> kann bei dem Hamming-Code nur spezifische ganzzahlige Werte annehmen, die sich aus der Bildungsvorgabe dieses Codes ergeben. Die Bitkombinationen in dem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bit umfassenden Datenblock können grundsätzlich beliebig gewählt werden, das heißt, es sind alle beliebigen Bitkombinationen zulässig.

Das Codewort des Hamming-Codes wird aus dem Datenwort durch Integration zusätzlicher Kontrollstellen, der sogenannten Paritätsbits, gewonnen. Dabei wird in jedes Datenwort von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Bit Länge eine feste Anzahl von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Kontrollstellen eingefügt. Daraus ergibt sich das Codewort mit einer Länge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=n+k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=n+k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/66b3c6e8ffc0bbc6b7a8b03d4b099e755f1fd024.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.608ex; height:2.343ex;" alt="{\displaystyle N=n+k}" loading="lazy">. Für ein Codewort sind, da die Kontrollstellen <a href="Redundanz_(Informationstheorie)" title="Redundanz (Informationstheorie)">redundante</a> aus dem Datenblock abgeleitete Information tragen, nur noch bestimmte Bitkombinationen möglich. Das ermöglicht sowohl Fehlererkennung als auch Fehlerkorrektur.

Die Vorgabe zur Codebildung durch eine weitere Gleichung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> ist in folgender Form beschrieben:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=2^{k}-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd63a2bf3390940415aaee3601a6ff497a136cf1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.416ex; height:2.843ex;" alt="{\displaystyle N=2^{k}-1}" loading="lazy"></dd></dl>

Dies bedeutet, dass wenn beispielsweise drei binäre Stellen für Kontrollbits (Paritätsbits) zur Verfügung stehen, das Codewort zwangsläufig eine Länge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=7}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=7}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fab558c861cc73a289c14d12cc4f0c81dce9b5b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.325ex; height:2.176ex;" alt="{\displaystyle N=7}" loading="lazy"> aufweisen muss. Für das Datenwort ergibt sich dann eine Länge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=7-3=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=7-3=4}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/545cb1efe9a9de80e492dbfc3e51d095980ac411.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.919ex; height:2.343ex;" alt="{\displaystyle n=7-3=4}" loading="lazy"> Bits pro Codewort oder allgemein:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{k}-k-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97eaeda8bd9ef60b365a6e578a84b9a4c2535f0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.799ex; height:2.843ex;" alt="{\displaystyle n=2^{k}-k-1}" loading="lazy"></dd></dl>

In der folgenden Tabelle sind alle möglichen Hamming-Codes unterschiedlicher Codewortlängen bis zur Blockgröße von 255 Bits dargestellt:

<th colspan="4">Parameterkombinationen bei Hamming-Codes

</th></tr>

<th>n

</th>

<th>k

</th>

<th>N = n + k

</th>

<th>n / (n + k)

</th></tr>

<tr>

<th>2k – k – 1

</th>

<th>

</th>

<th>2k – 1

</th>

<th>(2k – k – 1) / (2k – 1)

</th></tr>

<tr>

<th>Datenbits (Datenwort)

</th>

<th>Paritätsbits (Kontrollstellen)

</th>

<th>Nachrichtenbits (Gesamtlänge des Codewortes)

</th>

<th>Datenrate

</th></tr>

<tr>

<td>1

</td>

<td>2

</td>

<td>3

</td>

<td>1/3 ≈ 0,333

</td></tr>

<tr>

<td>4

</td>

<td>3

</td>

<td>7

</td>

<td>4/7 ≈ 0,571

</td></tr>

<tr>

<td>11

</td>

<td>4

</td>

<td>15

</td>

<td>11/15 ≈ 0,733

</td></tr>

<tr>

<td>26

</td>

<td>5

</td>

<td>31

</td>

<td>26/31 ≈ 0,839

</td></tr>

<tr>

<td>57

</td>

<td>6

</td>

<td>63

</td>

<td>57/63 ≈ 0,905

</td></tr>

<tr>

<td>120

</td>

<td>7

</td>

<td>127

</td>

<td>120/127 ≈ 0,945

</td></tr>

<tr>

<td>247

</td>

<td>8

</td>

<td>255

</td>

<td>247/255 ≈ 0,969

</td></tr></tbody></table>

Zur Klassifikation der unterschiedlich langen Hamming-Codes wird in der Literatur meist folgende Schreibweise verwendet: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N,n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b04cd919a39646f0860598dceaf668e8d9ff043e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.302ex; height:2.843ex;" alt="{\displaystyle (N,n)}" loading="lazy">-Code. Die erste Zahl gibt die Anzahl der Nachrichtenbits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ef1affa0ad7069851b8f0f7cd33359ad049813a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.873ex; height:2.843ex;" alt="{\displaystyle (N)}" loading="lazy"> des Codewortes an, die zweite Zahl die Anzahl der Datenbits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6dcf3083121187f661e0add2f50615aa21428e68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.204ex; height:2.843ex;" alt="{\displaystyle (n)}" loading="lazy"> pro Codewort. Vor allem in Demonstrationsbeispielen ist der Einfachheit wegen oft der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code anzutreffen. Für reale Anwendungen ist hier der Overhead, d. h. das Verhältnis von Kontrollbits zu Datenbits, zu ungünstig, weshalb längere Hamming-Codes wie der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (63,57)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (63,57)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14d3180d66227d203992cb43905b7f3f73d69471.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle (63,57)}" loading="lazy">-Hamming-Code verwendet werden.

Manchmal wird bei der Klassifizierungsangabe noch die Distanz des Codes als dritte Stelle angegeben. Wegen der festen Hamming-Distanz wird jedoch zumeist statt „<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (63,57,3)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (63,57,3)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7b6b39dd9e4a32580fa9246f44d05d17c4e6938.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.689ex; height:2.843ex;" alt="{\displaystyle (63,57,3)}" loading="lazy">-Hamming-Code“ nur „<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (63,57)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (63,57)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/14d3180d66227d203992cb43905b7f3f73d69471.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle (63,57)}" loading="lazy">-Hamming-Code“ geschrieben.

<div class="mw-heading mw-heading3"><h3 id="Berechnung_der_Paritätsstellen">Berechnung der Paritätsstellen</h3></div>

Die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Paritätsstellen (Kontrollbits) in einem Codewort werden nach einem Verfahren berechnet, wie es auch bei dem einfachen <a href="Parit%C3%A4tsbit" title="Paritätsbit">Paritäts-Prüfbit</a> zur Anwendung kommt. Im Regelfall wird vereinbarungsgemäß eine <a href="Parit%C3%A4tsbit#Gerade_und_ungerade_Parität" title="Paritätsbit">gerade Parität</a> für alle Kontrollstellen gewählt: Ist die Anzahl der logischen-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> der in die jeweilige Kontrollstelle eingerechneten Datenbitstellen eine gerade Anzahl, ist das jeweilige Paritätsbit logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">. Ist die Anzahl der logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> in den Datenbitstellen eine ungerade Anzahl, wird das jeweilige Paritätsbit auf logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> gesetzt, so dass sich als Summe der Datenbitstellen und der Paritätsbits immer eine gerade Anzahl von logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> Bits ergibt.

Die einzelnen Paritätsbits eines Codewortes werden nicht über alle Stellen (Bits) des Datenwortes gebildet, sondern nur über einzelne, ausgewählte Datenbits. Zur Konstruktion, welche Datenbitstellen in welche Kontrollbits eingerechnet werden, kann nach einer anschaulichen Methode vorgegangen werden. Zunächst wird dazu der Rahmen des Codewortes aus den Datenbits und den Kontrollstellen gebildet:

<ol><li>Im Codewort befinden sich an denjenigen Positionen, die Zweierpotenzen sind (1, 2, 4, 8, 16, …), die einzelnen Paritäts-Kontrollbits p.</li>

<li>Die Datenbits d des zu übertragenden Datenwortes werden dazwischen auf den freien Stellen im Codewort von links aufsteigend eingetragen.</li></ol>

Sind <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1},p_{2},\ldots ,p_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1},p_{2},\ldots ,p_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ff015013f87789d5ed926d27b67d35ccbd68bcf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:13.007ex; height:2.009ex;" alt="{\displaystyle p_{1},p_{2},\ldots ,p_{k}}" loading="lazy">Paritätsbits, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{1},d_{2},\ldots ,d_{N-k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{1},d_{2},\ldots ,d_{N-k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b19bcac220ac6856f08e967230c467b39f5075af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.774ex; height:2.509ex;" alt="{\displaystyle d_{1},d_{2},\ldots ,d_{N-k}}" loading="lazy"> Bits des Datenwortes und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1},c_{2},\ldots ,c_{N}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1},c_{2},\ldots ,c_{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c27deea949fec7eaea38a5573c676e6e262d1cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.033ex; height:2.009ex;" alt="{\displaystyle c_{1},c_{2},\ldots ,c_{N}}" loading="lazy"> die Bits des zu bildenden Codewortes, hat ein Codewort des so konstruierten Hamming-Code die folgende Form (diese Darstellung kann für größere Codewortlängen entsprechend erweitert werden):

In das erste Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> wird jedes zweite Datenbit, bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1dc52bfbaf6e577fbed72a716068f4533700bd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{3}}" loading="lazy"> angefangen, mit einbezogen. Für das erste Paritätsbit ergeben sich als Folge von Codewortstellen somit alle Datenbits, die an ungerade Position im Codewort stehen:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1}=p_{1}=c_{3}\oplus c_{5}\oplus c_{7}\oplus c_{9}\oplus c_{11}\oplus c_{13}\oplus c_{15}\oplus c_{17}\oplus c_{19}\oplus \cdots }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aba168344c99cc96360f023dd2e1a0ecd96a3f8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:61.428ex; height:2.343ex;" alt="{\displaystyle c_{1}=p_{1}=c_{3}\oplus c_{5}\oplus c_{7}\oplus c_{9}\oplus c_{11}\oplus c_{13}\oplus c_{15}\oplus c_{17}\oplus c_{19}\oplus \cdots }" loading="lazy"></dd></dl>

Das Symbol <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy"> ist die logische <a href="XOR" class="mw-redirect" title="XOR">XOR</a>-Funktion und stellt zugleich die Bildungsvorschrift für die Kontrollbits dar. Wie weiter mit Hilfe obiger Tabelle zu erkennen ist, kommen an den angeführten Bitpositionen im Codewort auf der rechten Seite der Gleichung nur Datenbits vor. Dies gilt für alle Paritätsbits.

In das zweite Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy"> wird das rechts von p2 im Codewort stehende Bit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1dc52bfbaf6e577fbed72a716068f4533700bd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{3}}" loading="lazy"> einberechnet, dann werden zwei Stellen im Codewort übersprungen, die nächsten zwei Bit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{6}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{6}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87670df150c1e4444386652b709c7a72106b8bcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{6}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{7}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67c5bf4c3a3a4d9883e64a807be8f898def72c29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.061ex; height:2.009ex;" alt="{\displaystyle c_{7}}" loading="lazy"> einberechnet, wieder zwei Stellen übersprungen, und so weiter. Statt eines Datenbits werden also zwei benachbarte Datenbits genommen und im Codewort zwei Stellen übersprungen. Damit ergibt sich für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy"> die Bildungsvorschrift:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{2}=p_{2}=c_{3}\oplus c_{6}\oplus c_{7}\oplus c_{10}\oplus c_{11}\oplus c_{14}\oplus c_{15}\oplus c_{18}\oplus c_{19}\oplus \cdots }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d300498abb2aad3b088b07492eb55a5d743c4eda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:62.25ex; height:2.343ex;" alt="{\displaystyle c_{2}=p_{2}=c_{3}\oplus c_{6}\oplus c_{7}\oplus c_{10}\oplus c_{11}\oplus c_{14}\oplus c_{15}\oplus c_{18}\oplus c_{19}\oplus \cdots }" loading="lazy"></dd></dl>

In das dritte Paritätsbit p3 werden die rechts im Codewort folgenden drei Stellen einberechnet, es werden vier Stellen des Codewortes übersprungen, dann vier Bit einberechnet, dann vier Stellen übersprungen, und so weiter. Es werden also Gruppen zu je vier Bits für die Bildung des Paritätsbits herangezogen. Damit ergibt sich für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a79626b787857474daa665c953bbc6725e7c345.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{3}}" loading="lazy">:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{4}=p_{3}=c_{5}\oplus c_{6}\oplus c_{7}\oplus c_{12}\oplus c_{13}\oplus c_{14}\oplus c_{15}\oplus c_{20}\oplus \cdots }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/204561bac75861bcf6f51f385128b98a9d8ba191.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:56.527ex; height:2.343ex;" alt="{\displaystyle c_{4}=p_{3}=c_{5}\oplus c_{6}\oplus c_{7}\oplus c_{12}\oplus c_{13}\oplus c_{14}\oplus c_{15}\oplus c_{20}\oplus \cdots }" loading="lazy"></dd></dl>

Das Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5bab39399bf5424f25d957cdc57c84a0622626d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.059ex; height:2.009ex;" alt="{\displaystyle p_{i}}" loading="lazy"> wird also über alle Stellen cj des Codeworts berechnet, in denen an der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-ten Stelle der <a href="Dualsystem" title="Dualsystem">Binärkodierung</a> des Index j eine logische Eins steht. Nach diesem Verfahren wird für die restlichen Paritätsbits analog fortgefahren, bis alle Paritätsbits des gewählten Hamming-Codes bestimmt sind. Das Bestimmen des Codeworts wird in praktischen Applikationen durch den sogenannten Encoder vorgenommen.

Im konkreten Fall des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code ergibt sich so die nachfolgende Codeworttabelle. Darunter sind in den jeweiligen Spalten die Verknüpfungen der einzelnen Paritätsbits eingetragen, aus denen sich unmittelbar die später dargestellte Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">, auch Prüfmatrix genannt, für dieses Beispiel ergibt. In den Spalten der letzten drei Zeilen sind Pfeile an jenen Stellen eingetragen, wo sich in der Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> dann logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> finden. Nach diesem Muster kann mit etwas Aufwand die Kontrollmatrix bei jedem Hamming-Code bestimmt werden. Es ist pro Zeile immer ein Paritätsbit mit einem aufwärts gerichteten Pfeil (↑) eingezeichnet, und die Datenbits zur Bestimmung des betreffenden Paritätsbits sind mit einem abwärtsgerichteten Pfeil (↓) markiert.

<th colspan="7">Bestimmung der Paritätsbits am Beispiel des (7,4)-Hamming-Code

</th></tr>

<th>c1

</th>

<th>c2

</th>

<th>c3

</th>

<th>c4

</th>

<th>c5

</th>

<th>c6

</th>

<th>c7

</th></tr>

<tr>

<td>p1

</td>

<td>p2

</td>

<td>d1

</td>

<td>p3

</td>

<td>d2

</td>

<td>d3

</td>

<td>d4

</td></tr>

<tr>

<td>↑

</td>

<td>

</td>

<td>↓

</td>

<td>

</td>

<td>↓

</td>

<td>

</td>

<td>↓

</td></tr>

<tr>

<td>

</td>

<td>↑

</td>

<td>↓

</td>

<td>

</td>

<td>

</td>

<td>↓

</td>

<td>↓

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>↑

</td>

<td>↓

</td>

<td>↓

</td>

<td>↓

</td></tr></tbody></table>

Die Anordnung von Paritäts- und Datenbits ist hierbei willkürlich gewählt. Es kann ohne Einschränkung eine andere Abfolge der einzelnen Bits im Codewort gewählt werden, ohne die Eigenschaft des Hamming-Codes zu ändern. Dieser Umstand wird im nachfolgenden systematischen oder auch separierbaren Hamming-Code genutzt, bei dem zur Bildung des Codeworts die Paritätsbits immer ans Ende des Datenwortes angehängt werden. Der separierbare Hamming-Code wird nach der gleichen Bildungsvorschrift gewonnen, ist aber durch eine andere Anordnung der Zeilen in der Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> und damit verbunden andere Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> gekennzeichnet.

<div class="mw-heading mw-heading3"><h3 id="Kürzester_Hamming-Code">Kürzester Hamming-Code</h3></div>

Der kürzeste Hamming-Code ist der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (3,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (3,1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8933db1c87b5fefc8d54c6e2d157e4b343bb8b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (3,1)}" loading="lazy">-Hamming-Code. Dabei wird ein Nutzdatenbit einem drei Bit langen Codewort zugeordnet. Mit obiger allgemeiner Berechnung ergibt sich, dass die beiden „Paritätsbits“ <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy"> nur in diesem Fall direkt dem einen Nutzdatenbit entsprechen. Es kann nur die beiden gültigen Codewörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 000}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 000}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5e4fc6c26318e380f08d4ace964300ab36ebc789.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 000}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 111}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 111}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/64431fec31ab6dfd5980a35f4056e5bef3c1fde4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 111}" loading="lazy"> geben. Die ungültigen Codewörter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 001}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 001}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9d35f1a0f903084523da480c8d27bf584855852d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 001}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 010}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 010}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3180a39e7c7e0d3db5ba787cf150f12c160a5997.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 010}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 100}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0572cd017c6d7936a12737c9d614a2f801f94a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 100}" loading="lazy"> werden bei der Decodierung mittels des Verfahrens der Mehrheitsentscheidung dem Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 000}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 000}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5e4fc6c26318e380f08d4ace964300ab36ebc789.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 000}" loading="lazy"> zugewiesen. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 110}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 110}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/61d2b914b923dff8ccc0236742b94ae745f1fed8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 110}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 101}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 101}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03a2f2ba5c3a850b0cc3d7efb40a3a7442ec6acc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 101}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 011}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 011}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/152a8c0bd45fda862cfe86f4720c2b14e0ff899a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 011}" loading="lazy"> dem Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 111}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 111}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/64431fec31ab6dfd5980a35f4056e5bef3c1fde4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 111}" loading="lazy">. Damit ist der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (3,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (3,1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8933db1c87b5fefc8d54c6e2d157e4b343bb8b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (3,1)}" loading="lazy">-Hamming-Code als ein Spezialfall gleich einem <a href="Wiederholungscode" title="Wiederholungscode">Wiederholungscode</a> mit einer Länge von 3. Der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (3,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (3,1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8933db1c87b5fefc8d54c6e2d157e4b343bb8b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (3,1)}" loading="lazy">-Hamming-Code ist auch der einzige Hamming-Code, der nur durch die Angabe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (3,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (3,1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8933db1c87b5fefc8d54c6e2d157e4b343bb8b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (3,1)}" loading="lazy"> eindeutig im Aufbau des Codewortes spezifiziert ist.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Korrekturleistungen">Korrekturleistungen</h3></div>

Der Hamming-Code weist, unabhängig von der gewählten Blockgröße, immer eine Distanz von drei auf. Dies bedeutet, dass sich benachbarte Codewörter immer um drei Bits unterscheiden. Tritt ein Fehler an einer Stelle eines Codeworts auf, wird dieses als ungültig erkannt und kann eindeutig dem richtigen Codewort zugeordnet, der Übertragungsfehler also korrigiert werden. Treten hingegen zwei Fehler in einem Codewort auf, funktioniert diese Zuordnung nicht mehr – die Korrektur des Decoders ordnet das empfangene Codewort fälschlich einem anderen zu. Dies wird als „Falschkorrektur“ bezeichnet. Eine andere Form des Versagens tritt bei drei Übertragungsfehlern auf: Hier erkennt der Decoder das fehlerhafte Codewort als gültig an.

Hamming-Codes können also nur einen Bitfehler pro Datenwort korrekt korrigieren. Wegen seiner Fähigkeit, alle empfangenen Codewörter einem validen Codewort zuordnen zu können, ist der Hamming-Code ein <a href="Perfekter_Code" title="Perfekter Code">perfekter Code</a>. Die meisten anderen Binärcodes – etwa der erweiterte Hamming-Code – sind nicht perfekt. Bei diesen Codes können durch Übertragungsfehler Codewörter auftreten, die der Decoder zwar als falsch erkennen kann, jedoch keinem gültigen Wort zuordnen kann (Dekodierversagen).

<div class="mw-heading mw-heading3"><h3 id="Linearität">Linearität</h3></div>

Hamming-Codes sind grundsätzlich <a href="Linearer_Code" title="Linearer Code">lineare Codes</a>. Bei diesen – auch als binäre Gruppencodes bezeichneten – Codierungen führt jede Modulo-2-Addition (<a href="XOR-Verkn%C3%BCpfung" class="mw-redirect" title="XOR-Verknüpfung">XOR-Verknüpfung</a>) zweier Codewörter wieder zu einem gültigen Codewort. Zu den Voraussetzungen eines linearen Codes zählt die Existenz eines neutralen Elements. Im Falle eines Hamming-Codes bedeutet dies, dass das Nullwort – dessen Stellen sämtlich logisch-'0' sind – gültig sein muss. Das sogenannte „Codegewicht“ entspricht somit bei Hamming-Codes dem Hamming-Abstand von drei.

Eine weitere allgemeine Eigenschaft von Gruppencodes besteht darin, dass sich die einzelnen gültigen Codewörter c aus einer Generatormatrix G und den Datenwörtern d nach folgender Form erzeugen lassen:

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {c} =\mathbf {G} \cdot \mathbf {d} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74acce07c4d12f077fc22716fc3464dbcd3f8c57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.552ex; height:2.176ex;" alt="{\displaystyle \mathbf {c} =\mathbf {G} \cdot \mathbf {d} }" loading="lazy"></dd></dl>

Aus dieser Gleichung ergibt sich mit der im vorherigen Abschnitt dargestellten Bildungsvorschrift und den Rechenregeln für <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrizen</a> für einen nicht separierbaren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code, die folgende Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">:

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {G} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\{\color {Brown}1}&{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}0}\\0&1&1&1\\{\color {Brown}0}&{\color {Brown}1}&{\color {Brown}0}&{\color {Brown}0}\\{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}1}&{\color {Brown}0}\\{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}1}\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a7f2b067a5adcc0cb63992af8a6d3b32b7dec7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:22.282ex; height:22.343ex;" alt="{\displaystyle \mathbf {G} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\{\color {Brown}1}&{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}0}\\0&1&1&1\\{\color {Brown}0}&{\color {Brown}1}&{\color {Brown}0}&{\color {Brown}0}\\{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}1}&{\color {Brown}0}\\{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}1}\\\end{pmatrix}}}" loading="lazy"></dd></dl>

Die ersten beiden Zeilen der Matrix bilden die ersten beiden Paritätsbits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy"> des Codewortes. Die Einsen der Zeilen geben hierbei an, welche Datenbitstellen in das jeweilige Paritätsbit eingerechnet werden. Die dritte Zeile, ebenso wie alle nachfolgenden Zeilen mit nur einer Eins pro Zeile, bilden die Datenbits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/858aa7b9662c90d0e01c9615aac9b1fdd84a02dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.427ex; height:2.509ex;" alt="{\displaystyle d_{n}}" loading="lazy"> im Codewort ab. Die vierte Zeile bildet das dritte Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a79626b787857474daa665c953bbc6725e7c345.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{3}}" loading="lazy">.

Aus der Generatormatrix lässt sich direkt die Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> ableiten, die vom Decoder verwendet wird, um fehlerhafte Bitstellen mittels <a href="Matrixmultiplikation" class="mw-redirect" title="Matrixmultiplikation">Matrixmultiplikation</a> zu erkennen. Die Kontrollmatrix muss jedes Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> auf den <a href="Nullvektor" title="Nullvektor">Nullvektor</a> abbilden:

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {H} \cdot \mathbf {c} =\mathbf {0} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e84bb075507206431a58abd69498186543906f6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.394ex; height:2.176ex;" alt="{\displaystyle \mathbf {H} \cdot \mathbf {c} =\mathbf {0} }" loading="lazy"></dd></dl>

Für obige Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> lässt sich die folgende Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> ermitteln:

</mrow>

<mrow>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {H} :={\begin{pmatrix}{\color {Brown}1}&{\color {Brown}0}&1&{\color {Brown}0}&1&0&1\\{\color {Brown}0}&{\color {Brown}1}&1&{\color {Brown}0}&0&1&1\\{\color {Brown}0}&{\color {Brown}0}&0&{\color {Brown}1}&1&1&1\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/110af6b9c4d4013cd5c66961a479db0712a749cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:32.728ex; height:9.176ex;" alt="{\displaystyle \mathbf {H} :={\begin{pmatrix}{\color {Brown}1}&{\color {Brown}0}&1&{\color {Brown}0}&1&0&1\\{\color {Brown}0}&{\color {Brown}1}&1&{\color {Brown}0}&0&1&1\\{\color {Brown}0}&{\color {Brown}0}&0&{\color {Brown}1}&1&1&1\\\end{pmatrix}}}" loading="lazy"></dd></dl>

Der Inhalt der Matrix kann hierbei beispielsweise über das im vorigen Abschnitt vorgestellte tabellarische Verfahren zur Bestimmung der Paritätsbits aus der Generatormatrix gewonnen werden.

Tritt ein einzelner <a href="Bitfehler" title="Bitfehler">Bitfehler</a> auf, so gilt für das entstehende ungültige Codewort:

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {H} \cdot \mathbf {c} \neq \mathbf {0} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a394aac0728f68380ac427ac19ceff5b0168cf2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.394ex; height:2.676ex;" alt="{\displaystyle \mathbf {H} \cdot \mathbf {c} \neq \mathbf {0} }" loading="lazy"></dd></dl>

Durch den Wert dieser Gleichung kann über eine Syndromtabelle die fehlerhafte Bitstelle eindeutig bestimmt und durch Invertieren korrigiert werden.

Eine spielerische Anwendung speziell des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Codes findet man bei der Lösung von <a href="Eberts_Hutproblem" title="Eberts Hutproblem">Eberts Hutproblem</a>.

<div class="mw-heading mw-heading3"><h3 id="Systematischer_Hamming-Code">Systematischer Hamming-Code</h3></div>

Aufgrund der Linearität können beliebige Zeilen der Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> vertauscht werden, ohne die Codeeigenschaften zu verändern. Die jeweilige Form der Generatormatrix muss nur zwischen Encoder und Decoder abgestimmt sein. Ein systematischer Code liegt vor, wenn im Codewort zuerst alle Datenbits dn und nachfolgend alle Paritätsbits pn angeordnet sind. Durch die Separierbarkeit können Encoder und Decoder schaltungstechnisch in elektronischen digitalen Schaltungen wie <a href="Anwendungsspezifische_integrierte_Schaltung" title="Anwendungsspezifische integrierte Schaltung">ASICs</a> oder <a href="FPGA" class="mw-redirect" title="FPGA">FPGAs</a> mit weniger Speicheraufwand und mit geringerer <a href="Verz%C3%B6gerung_(Telekommunikation)" title="Verzögerung (Telekommunikation)">Latenzzeit</a> realisiert werden. Separierbare Codes werden auch als „systematische Codes“ bezeichnet.

Obige Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> kann durch Umstellen der Zeilen auf folgende Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">′ so umgeformt werden, dass der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code ein systematischer Code wird. Eine mögliche Generatormatrix des systematischen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Codes lautet:

<msup>

</msup>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {G'} :={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&0&1\\1&0&1&1\\0&1&1&1\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6700db62810b57be4758da9023d78f750099dfb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:22.967ex; height:22.343ex;" alt="{\displaystyle \mathbf {G'} :={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&0&1\\1&0&1&1\\0&1&1&1\\\end{pmatrix}}}" loading="lazy"></dd></dl>

Die assoziierte Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">′ kann leichter bestimmt werden, denn bei systematischer Blockcodes gilt mit Modulo-2-Operationen:

<msup>

</msup>

</mrow>

<msup>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {H'} \cdot \mathbf {G'} =\mathbf {0} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/571c63ce40cde8e846774daf93c347f64c265c8a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.676ex; height:2.509ex;" alt="{\displaystyle \mathbf {H'} \cdot \mathbf {G'} =\mathbf {0} }" loading="lazy"></dd></dl>

Damit bestimmt sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">′ zu:

<msup>

</msup>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {H'} :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3a554ad1685d8eb314abd66a3892242175a2e579.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:33.413ex; height:9.176ex;" alt="{\displaystyle \mathbf {H'} :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}}" loading="lazy"></dd></dl>

Die ersten 4 Spalten der Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">′ bestehen dabei aus den letzten drei Zeilen der Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">′. Der rechte Teil der Kontrollmatrix ist mit der <a href="Einheitsmatrix" title="Einheitsmatrix">Einheitsmatrix</a> aufgefüllt.

Damit ist dargestellt, dass nur die Angabe <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code für eine konkrete Implementierung nicht eindeutig den genauen Codierungsvorgang und Decodierungsvorgang beschreibt. Dies ist erst durch Angabe der jeweiligen Generatormatrix, oder bei zyklischen Hamming-Codes durch das Generatorpolynom, gewährleistet.

<div class="mw-heading mw-heading3"><h3 id="Zyklischer_Hamming-Code">Zyklischer Hamming-Code</h3></div>

Bei der praktischen Anwendung spielen <a href="Zyklischer_Code" title="Zyklischer Code">zyklische Codes</a>, insbesondere zyklische separierbare Hamming-Codes, eine bedeutende Rolle. Mit diesen kann die Berechnung der einzelnen Prüfbits im Encoder und die Decodierung im Decoder mit minimalen Speicheraufwand in Form von <a href="Linear_r%C3%BCckgekoppeltes_Schieberegister" title="Linear rückgekoppeltes Schieberegister">linear rückgekoppelten Schieberegistern</a> (LFSR) realisiert werden. Zyklische Codes sind lineare Codes, bei denen zusätzlich noch die Forderung gilt, dass eine Rotation oder zyklische Verschiebung eines Codewortes wiederum auf ein gültiges Codewort führen muss.

Der zyklische Hamming-Code kann allgemein in der Beschreibung äquivalent auch als eine Untergruppe der <a href="BCH-Code" title="BCH-Code">BCH-Codes</a> (Bose-Chaudhuri-Hocquenghem-Codes) aufgefasst werden. BCH-Codes sind eine sehr große Gruppe von zyklischen Blockcodes, die in ihren Parametern und Aufbau stärker als die Hamming-Codes variiert werden können.

Die Erzeugung zyklischer Hamming-Codes wird je nach Blocklänge durch <a href="Primitives_Polynom" title="Primitives Polynom">primitive Generatorpolynome</a> von entsprechendem <a href="Polynom" title="Polynom">Grad</a> vorgenommen. Das Generatorpolynom kann direkt im LFSR zum Berechnen der Paritätsbits abgebildet werden.

In folgender Tabelle sind beispielhaft übliche Generatorpolynome angeführt. Es können in konkreten Implementierungen aber auch andere Generatorpolynome gewählt werden, ohne die Eigenschaften des Hamming-Codes zu ändern, so das gewählte Polynom nur primitiv ist und zwischen Encoder und Decoder vereinbart ist:

<th colspan="4">Zyklische Hamming-Codes

</th></tr>

<th>k

</th>

<th>N

</th>

<th>n

</th>

<th>Generatorpolynom G(z)

</th></tr>

<tr>

<td>2

</td>

<td>3

</td>

<td>1

</td>

<td>z2 + z + 1

</td></tr>

<tr>

<td>3

</td>

<td>7

</td>

<td>4

</td>

<td>z3 + z + 1

</td></tr>

<tr>

<td>4

</td>

<td>15

</td>

<td>11

</td>

<td>z4 + z + 1

</td></tr>

<tr>

<td>5

</td>

<td>31

</td>

<td>26

</td>

<td>z5 + z2 + 1

</td></tr>

<tr>

<td>6

</td>

<td>63

</td>

<td>57

</td>

<td>z6 + z + 1

</td></tr>

<tr>

<td>7

</td>

<td>127

</td>

<td>120

</td>

<td>z7 + z3 + 1

</td></tr>

<tr>

<td>8

</td>

<td>255

</td>

<td>247

</td>

<td>z8 + z7 + z2 + z + 1

</td></tr>

<tr>

<td>9

</td>

<td>511

</td>

<td>502

</td>

<td>z9 + z4 + 1

</td></tr></tbody></table>

Bemerkungen:

<ul><li>z ist eine alternative Schreibweise für z1: z6 + z + 1  →  z6 + z1 + 1</li>

<li>1 ist eine alternative Schreibweise für z0: z6 + z + 1  →  z6 + z1 + z0</li>

<li>Die Anzahl der Terme ist immer ungerade und enthält immer die Potenzen zk und 1: z6 + z + 1</li>

<li>Man kann immer die Exponenten spiegeln, d. h. alle xl durch xk−l ersetzen, es entsteht ein anderer, aber genau funktionierender zyklischer Blockcode: z6 + z + 1  →  z6 + z1 + z0  →  z0 + z5 + z6  →  z6 + z5 + 1</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Praktische_Realisierung_eines_Hamming-Encoders">Praktische Realisierung eines Hamming-Encoders</h2></div>

Zyklische separierbare Hamming-Codes lassen sich schaltungstechnisch in digitalen elektrischen Schaltungen einfach realisieren. In nebenstehender Abbildung ist zur Veranschaulichung ein <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (15,11)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (15,11)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6099df9c3832bb0a921994e25ae7368098e1045b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle (15,11)}" loading="lazy">-Hamming Encoder mit Generatorpolynom <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z^{4}+z+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z^{4}+z+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9ce172b1b16669d06bcf47aa50451f9697d12d35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.076ex; height:2.843ex;" alt="{\displaystyle z^{4}+z+1}" loading="lazy"> dargestellt.

In der Darstellung werden die Datenbits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> als serieller Datenstrom in der Mitte oben eingelesen und rechts das Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> seriell ausgegeben. Die Schalter befinden sich zunächst in Stellung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">: Damit werden im Codewort zunächst die Datenbits direkt ausgegeben und gleichzeitig in das LFSR geschoben. Sind alle Datenbits eines Datenwortes eingelesen, wechseln die beiden Schalter in Stellung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">: Es wird nun bitweise der Inhalt des LFSR ausgegeben, der den Paritätsbits <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> entspricht. Sind alle Prüfstellen ausgegeben, wiederholt sich der Vorgang. Zur Vereinfachung sind die nötigen Taktleitungen und Synchronisationsschaltungen nicht dargestellt.

Der Hamming-Decoder gestaltet sich ähnlich: Der empfangene, serielle Bitdatenstrom von den Codewörtern wird in ein entsprechendes LFSR geschoben und gleichzeitig in einer separaten Schieberegisterkette zwecks Latenzanpassung geschoben. Der Inhalt des LFSR beim Decoder dient nach dem kompletten Empfang eines Codewortes als Adresszeiger in einem Syndromspeicher, der meist als eine fixe <a href="Festwertspeicher" title="Festwertspeicher">ROM-Tabelle</a> in der Schaltung realisiert ist. Der Datenausgang des Syndromspeichers wirkt dabei direkt auf den seriellen Datenstrom der Datenbits ein und korrigiert bei Bedarf fehlerhaft erkannte Datenbitstellen durch Invertieren.

<div class="mw-heading mw-heading2"><h2 id="Decodierung">Decodierung</h2></div>

Bei der Decodierung können verschiedene Verfahren angewendet werden, die sich in der Komplexität des Decoders und Decoderleistung unterscheiden. Ein wesentliches Verfahren basiert auf der oben ermittelten Syndromtabelle, die Aufschluss darüber gibt, welche Stelle im Codewort falsch ist. Dies ist bei empfangenen oder gelesenen binären Symbolen ein relativ einfaches Verfahren. Allerdings ist kein allgemeines Verfahren bekannt, mit dem ein linearer Blockcode beliebiger Codewortlänge deterministisch in <a href="Polynomialzeit" title="Polynomialzeit">Polynomialzeit</a> decodierbar wäre. Bei einem (N,n)-Hamming-Code ist der Decodierungsaufwand von der Codewortlänge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> abhängig und steigt exponentiell. Durch Verwendung des Syndroms bei der Decodierung lässt sich die Anzahl der möglichen Fehlerkombinationen von 2N auf 2n reduzieren. In der <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a> wird die Zeitklasse jener Entscheidungsprobleme als <a href="NP-schwer" class="mw-redirect" title="NP-schwer">NP-schwer</a> bezeichnet.

Eine weitere Möglichkeit, die Decodierungsleistung zu verbessern, besteht in dem Umstand, dass in realen Nachrichtensystemen der Decoder die einzelnen Codewörter im Regelfall nicht als binäre, sondern als mehrstufige Signale erhält. Die empfangenen analogen Signale werden von einem vorgeschalteten <a href="Analog-Digital-Umsetzer" title="Analog-Digital-Umsetzer">Analog-Digital-Umsetzer</a> zunächst <a href="Quantisierung_(Signalverarbeitung)" title="Quantisierung (Signalverarbeitung)">quantisiert</a>. Die entstehenden Abstufungen des Signals zwischen logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> werden vom Decoder als Wahrscheinlichkeiten aufgefasst und das Codewort anhand dieser iterativ konstruiert. Diese Verfahrensweise wird in der meist englischsprachigen Fachliteratur als Soft-Decision bezeichnet und bewirkt einen höheren <a href="Codegewinn" title="Codegewinn">Codegewinn</a>.

Das Gegenstück dazu ist die sogenannte Hard Decision, die als ein Extremfall der Soft Decision aufgefasst werden kann. Dabei wird das analoge Empfangssignal vor der Decodierung mittels 1-Bit breiten Analog-Digital-Umsetzer, einem „<a href="Komparator_(Analogtechnik)" title="Komparator (Analogtechnik)">Komparator</a>“, als ein digitales Eingangssignal für die Codewörter abgebildet. Damit ist bereits vor der Decodierung festgelegt, ob ein bestimmtes Bit des empfangenen Codewortes logisch-'1' oder logisch-'0' ist.

<div class="mw-heading mw-heading3"><h3 id="Decodierung_mittels_Hard_Decision">Decodierung mittels Hard Decision</h3></div>

In diesem Fall liegen die empfangenen Codewörter bereits als digitale Folgen vor, weshalb sich der Decodierprozess in einem einstufigen Prozess auf die Auswertung der Syndromtabelle reduziert. Dieses Verfahren wird großteils dann verwendet, wenn der Decoder möglichst einfach gestaltet sein soll und keine „verketteten Codes“, d. h. aus Kombinationen unterschiedlicher Hamming-Codes bestehende, zum Einsatz kommen.

Bei der oben eingeführten Darstellung mittels Kontrollmatrix wurde bereits erläutert, dass das Produkt aus empfangenen Codewort <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> und der Kontrollmatrix bei einem Fehler einen Wert ungleich 0 annimmt:

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {H} \cdot \mathbf {c} \neq \mathbf {0} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a394aac0728f68380ac427ac19ceff5b0168cf2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.394ex; height:2.676ex;" alt="{\displaystyle \mathbf {H} \cdot \mathbf {c} \neq \mathbf {0} }" loading="lazy"></dd></dl>

Durch entsprechende Anordnung der Parity-Stellen, und damit infolge der Form der Kontrollmatrix, lässt sich im einfachsten Fall der Wert dieser Gleichung als Syndrom direkt zur Korrektur der betreffenden Bitstelle verwenden. Wenn diese Gleichung bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code den Wert 1 liefert, ist genau das erste Bit des empfangenen Codewortes falsch. Bei dem Wert 2 der Gleichung das zweite Bit, und so weiter. Durch <a href="Negation" title="Negation">Negation</a> der betreffenden Bitstelle im Codewort kann der Fehler korrigiert werden. Im fehlerfreien Fall liefert obige Gleichung den Wert 0, und keine Bitstelle wird korrigiert.

Diese einfache Übereinstimmung von Syndromwert zu fehlerhafter Bitstelle ist bei einem Hamming-Code nur dann der Fall, wenn sich die einzelnen Paritätsbits genau an den Positionen im Codewort befinden, die Zweierpotenzen darstellen. Dies ist bei der eingangs dargestellten Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> der Fall. Damit entfällt eine Syndromtabelle (ROM-Tabelle), die erst den jeweiligen Wert der Gleichung von Kontrollmatrix und Codewort auf eine bestimmte Bitposition umsetzt. Diese Vereinfachung für die Decodierung ist auch der Grund, warum Hamming-Codes in Beispielen meistens in der oben dargestellten Form der Generatormatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> vorgenommen werden.

Zur Decodierung des oben dargestellten separierbaren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code mit seiner Kontrollmatrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">′ ist hingegen zur Ermittlung der fehlerhaften Stelle im Codewort eine Umsetzung des Wertes aus der Prüfgleichung notwendig. Im fehlerfreien Fall liefert die Prüfgleichung, so wie bei allen Hamming-Codes, den Wert 0. Im Fehlerfall liefert sie einen Wert ungleich 0, der nicht der fehlerhaften Bitstelle im Codewort entsprechen muss. Die Umsetzung auf die fehlerhafte Bitstelle kann mittels eines <a href="Festwertspeicher" title="Festwertspeicher">ROM-Speichers</a> erfolgen, dessen Adressen den Wert der Kontrollmatrix erhält, und die Datenausgänge angeben, welche Bitstelle durch Invertierung zu korrigieren ist. Im Fall des oben angegebenen, separierbaren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Codes muss der ROM-Speicher folgenden Dateninhalt haben:

<th>Eingabewert (ROM-Speicheradresse)

</th>

<th>Ausgabewert (Fehlerhafte Bitposition im Codewort)

</th></tr>

<tr>

<td>0

</td>

<td>0

</td></tr>

<tr>

<td>1

</td>

<td>5

</td></tr>

<tr>

<td>2

</td>

<td>6

</td></tr>

<tr>

<td>3

</td>

<td>1

</td></tr>

<tr>

<td>4

</td>

<td>7

</td></tr>

<tr>

<td>5

</td>

<td>2

</td></tr>

<tr>

<td>6

</td>

<td>3

</td></tr>

<tr>

<td>7

</td>

<td>4

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

Das folgende Beispiel in <a href="Pseudocode" title="Pseudocode">Pseudocode</a> zeigt eine <a href="Funktion_(Programmierung)" title="Funktion (Programmierung)">Funktion</a>, die den Hamming-Code für das gegebene Datenwort der Länge n erzeugt und ihn als <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Array</a> zurückgibt. Der Hamming-Code hat n Datenbits und k <a href="Parit%C3%A4tsbit" title="Paritätsbit">Paritätsbits</a>.

<pre>/**

* hammingCode // Array für den Hamming-Code

* index // Position des Paritätsbits

* numberOfSetBits // Anzahl der gesetzten Bits

*/

function createHammingCode(dataWord, n, k)

{

for i := 0 to k - 1 do // for-Schleife, die die Position der Paritätsbits ermittelt

{

index := 2 ^ i - 1

hammingCode[index] := -1 // Setzt die Paritätsbits auf -1, um sie identifizieren zu können

}

j := 0

for i := 0 to k + n - 1 do // for-Schleife, die die Bits des Hamming-Code durchläuft

{

if (hammingCode[i] <> -1) // Wenn Datenbit, also kein Paritätsbit

{

hammingCode[i] := dataWord[j] // Setzt die Datenbits des Hamming-Code

j := j + 1

}

for i := 0 to k + n - 1 do // for-Schleife, die die Bits des Hamming-Code durchläuft

{

if (hammingCode[i] = -1) // Wenn Paritätsbit

{

index := log2(i + 1) // Logarithmus zur Basis 2

numberOfSetBits := 0

for j := i + 2 to k + n do

{

if (das Bit von j an der Position index ist gesetzt)

{

if (das Bit des Hamming-Code ist ebenfalls gesetzt)

{

numberOfSetBits := numberOfSetBits + 1 // Variable für die Anzahl der gesetzten Bits um 1 erhöhen

}

hammingCode[i] := numberOfSetBits mod 2 // Setzt die Paritätsbits des Hamming-Code für gerade Parität

}

return hammingCode // Gibt den Array mit dem Hamming-Code zurück

}

</pre>

<div class="mw-heading mw-heading2"><h2 id="Erweiterter_Hamming-Code">Erweiterter Hamming-Code</h2></div>

Da der Hamming-Code nur einen Bitfehler pro Datenwort erkennen und korrigieren kann und zwei Bitfehler pro Datenwort bei dem Decoder zu einem falschen Codewort führen, besteht der Wunsch, diese Eigenschaften zu verbessern. Dieser Code wird als „erweiterter Hamming-Code“ (englisch extended Hamming Code) bezeichnet. Dazu wird bei dem Hamming-Code ein weiteres Paritätsbit angefügt, in das alle binären Stellen des nicht erweiterten Hamming-Codes einfließen. Damit wird beispielsweise aus dem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (7,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (7,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af8653472974d61337b540dd5bc077a6c4ba5d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (7,4)}" loading="lazy">-Hamming-Code ein erweiterter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (8,4)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (8,4)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/62c0287545d37c96d00da483448be5f199d1f69d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.168ex; height:2.843ex;" alt="{\displaystyle (8,4)}" loading="lazy">-Hamming-Code.

Die Erweiterung eines allgemeinen Blockcodes um eine zusätzliche Kontrollstelle ist nur sinnvoll, wenn das „Codegewicht“ ungerade ist, da nur dann zusätzliche Information in diesem zusätzlichen Kontrollbit vorhanden ist. Dies ist bei Hamming-Codes mit einem Codegewicht von 3 immer erfüllt. Damit wird der Hamming-Abstand bei dem erweiterten Hamming-Code von 3 auf 4 erhöht, und der erweiterte Hamming-Code kann folgende Fehler pro Codewort erkennen bzw. korrigieren:

<ol><li>Er kann beliebig positionierte einzelne Bitfehler erkennen und korrigieren. In diesem Fall ist der Syndromwert ungleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und das zusätzliche Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">.</li>

<li>Er kann beliebig positionierte zweifache Bitfehler erkennen, aber nicht mehr korrigieren. In diesem Fall ist der Syndromwert ungleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und das zusätzliche Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">.</li>

<li>Er kann alle dreifachen Bitfehler entweder als ungültiges Codewort erkennen und weist bei der Decodierung ein gültiges Codewort zu, das nicht gesendet wurde, oder erkennt dreifache Bitfehler, die nicht korrigiert werden können. Welcher Fall eintritt, hängt von den Positionen der drei Bitfehler im Codewort ab. Im ersten Fall ist der Syndromwert ungleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und das zusätzliche Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">, im zweiten Fall ist der Syndromwert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und das zusätzliche Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">.</li>

<li>Vierfache Bitfehler eines Codewortes werden entweder als ungültiges und korrigierbares Codewort, wie im ersten Punkt erkannt, und einem gültigen Codewort zugewiesen, das nicht gesendet wurde. Oder es wird unmittelbar ein gültiges Codewort empfangen, das gar nicht gesendet wurde. Welcher Fall eintritt, hängt auch in hierbei davon ab, an welchen Bitpositionen im Codewort die Bitfehler auftreten. Im ersten Fall ist der Syndromwert ungleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und das zusätzliche Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">. Im zweiten Fall ist der Syndromwert <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> und das zusätzliche Paritätsbit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">, was einem gültigen Codewort entspricht. In jedem Fall werden bei vierfachen Bitfehlern andere als die gesendeten Codewörter ausgegeben, was als Decodierversagen bezeichnet wird.</li></ol>

Für den Decoder von erweiterten Hamming-Codes, der nur mittels Hard-Decision arbeitet, lässt sich damit folgende <a href="Wahrheitstabelle" title="Wahrheitstabelle">Wahrheitstabelle</a> aufstellen, nach deren Eingangsgrößen in Form des Syndromvektors und der zusätzlichen Parity-Prüfung der Decoder entscheiden kann, ob kein Fehler, ein korrigierbarer Fehler oder ein nicht korrigierbarer Fehler vorliegt:

<th>Syndromvektor

</th>

<th>zusätzliche Parity-Prüfung

</th>

<th>Aktion des Decoders

</th>

<th>Empfangenes Codewort

</th></tr>

<tr>

<td>= 0

</td>

<td>0

</td>

<td>kein Fehler

</td>

<td>gültig

</td></tr>

<tr>

<td>≠ 0

</td>

<td>1

</td>

<td>korrigierbarer Fehler

</td>

<td>ungültig

</td></tr>

<tr>

<td>= 0

</td>

<td>1

</td>

<td>korrigierbarer Fehler (im Paritätsbit)

</td>

<td>ungültig

</td></tr>

<tr>

<td>≠ 0

</td>

<td>0

</td>

<td>erkannter, nicht korrigierbarer Fehler

</td>

<td>ungültig

</td></tr></tbody></table>

Der erweiterte Hamming-Code ist kein perfekter Code, da nicht mehr alle ungültigen Codewörter eindeutig gültigen Codewörtern zugeordnet werden können. Was in den Fällen mit erkannten aber nicht korrigierbaren Datenfehlern passiert, müssen weitere Verarbeitungsebenen nach dem Hamming-Decoder entscheiden. Weiterhin kann bei drei oder mehr Bitfehlern pro Codewort ein „Decodierversagen“ auftreten. Das heißt, diese Mehrfachfehler werden entweder nicht erkannt oder nicht gesendeten gültigen Codewörtern zugewiesen. Dies ist vor allem bei Hamming-Codes mit langen Codewörtern zu beachten, da sich dieses Verhalten durch Wahl der Codewortlänge nicht verändert.

Anwendung findet der erweiterte Hamming-Code beispielsweise als sogenannter „innerer Blockcode“ in <a href="Turbo-Code" title="Turbo-Code">Turbo-Product-Codes</a>, wie sie in drahtlosen Funknetzen zur Datenübertragung nach dem Standard <a href="Institute_of_Electrical_and_Electronics_Engineers" title="Institute of Electrical and Electronics Engineers">IEEE</a> 802.16 im Rahmen von <a href="WiMAX" title="WiMAX">WiMAX</a> auf der Funkschnittstelle verwendet werden.

<div class="mw-heading mw-heading2"><h2 id="Codeverkürzung">Codeverkürzung</h2></div>

Sowohl der Hamming-Code als auch der erweiterte Hamming-Code können in der Länge ihrer Codewörter verkürzt werden, um in Anwendungen Codewörter mit bestimmter, fester Länge zu erhalten. Dies wird als Codeverkürzung bezeichnet. Alle Hamming-Codes weisen, wie dargestellt, nur vergleichsweise wenige wählbare Codewortlängen in groben Schrittweiten zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/76af5b5bc7d056faef7eef0c6efeea3a16adc156.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.254ex; height:2.843ex;" alt="{\displaystyle 2^{k}-1}" loading="lazy"> auf, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> ganzzahlig und größer 1 gewählt werden muss. Dazwischenliegende Codewortlängen sind bei dem Hamming-Code nicht möglich.

Durch das Verfahren der Codeverkürzung werden Codewortlängen zwischen diesen einzelnen groben Stufen wählbar, allerdings wird dieser Vorteil je nach Verfahren entweder durch ein schlechteres Verhältnis von Datenbitstellen (Nutzdaten) zur Anzahl der Kontrollstellen im Codewort erkauft, oder es wird durch das Verfahren die Mindestdistanz des Codes und damit seine Korrekturleistung reduziert.

Zur Codeverkürzung können grundsätzlich bei allen Codes folgende Verfahren zur Anwendung kommen:

<ol><li>Es werden auf Seite des Encoders nur jene möglichen Codewörter ausgewählt und anschließend als gültige Codewörter verwendet, die an den ersten oder letzten Stellen des Codewortes immer logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> sind. Je nach gewünschter resultierender Codewortlänge wird eine entsprechende Anzahl an Stellen ausgewählt, zwischen Encoder und Decoder vereinbart und im Verfahren nicht mehr geändert. Durch den Umstand, dass die weggelassenen Stellen immer bekannte Werte aufweisen, brauchen sie nicht mehr übertragen bzw. gespeichert zu werden: Das resultierende Codewort ist in seiner Länge verkürzt. Bei diesem Verfahren bleibt die Mindestdistanz des Hamming-Code von drei und somit seine Korrekturleistung erhalten. Es stellt sich allerdings ein ungünstigeres Verhältnis von Datenbitanteil zum Kontrollbitanteil im Codewort ein. Dies bedeutet, dass jene verkürzten Hamming-Codes einen größeren Anteil von Kontrollstellen (Paritätsbits) im Codewort aufweisen, als im Optimum bei Hamming-Codes mit unverkürzten Codewortlänge nötig wäre.</li>

<li>Es werden ausgewählte Stellen des Codewortes auf Seite des Encoder punktiert, das heißt gelöscht und auf einen festen Wert von entweder logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> oder logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> gesetzt. Durch den Umstand des festen Wertes brauchen die entsprechenden Binärstellen nicht mehr übertragen bzw. gespeichert zu werden, es ergibt sich eine entsprechende Längenreduktion des resultierenden Codewortes. Je nach Wahl der Stellen im Codewort ergeben sich unterschiedlich starke Reduktionen der Mindestdistanz des Codes. Da bei Hamming-Codes der Mindestabstand immer drei ist, würde eine Punktierung zu einem vollständigen Verlust der Korrekturleistung führen. Punktierungen haben daher bei Blockcodes wie dem Hamming-Code keine praktische Bedeutung und finden sich typischerweise bei <a href="Faltungscode" title="Faltungscode">Faltungscodes</a> mit entsprechend hohen Mindestabstand.</li></ol>

Praktische Anwendungen von verkürzten und erweiterten Hamming-Codes finden sich beispielsweise bei der Korrektur von einfachen Speicherfehlern und der sicheren Detektion von zweifachen Speicherfehlern pro Adresse bei <a href="Dynamic_Random_Access_Memory" title="Dynamic Random Access Memory">DRAM-Speichern</a>. Diese kostengünstigen Speicher benötigen pro Bit nur einen kleinen <a href="Kondensator_(Elektrotechnik)" title="Kondensator (Elektrotechnik)">Kondensator</a> zur Datenspeicherung, und es kann durch Störeffekte relativ leicht zur Bitfehlern kommen. Handelsübliche Speichermodule weisen pro Speicheradresse eine <a href="Bus_(Datenverarbeitung)" title="Bus (Datenverarbeitung)">Datenbusbreite</a> von typischerweise 36 Bit oder 72 Bit auf – beides sind Werte, die nicht direkt durch entsprechende Codewortlängen des Hamming-Codes erreicht werden können.

Durch die Codeverkürzung nach dem ersten Verfahren kann relativ einfach ein verkürzter Hamming-Code mit genau passender Codewortlänge konstruiert werden. In <a href="Applikationsschrift" class="mw-redirect" title="Applikationsschrift">Applikationsschriften</a> der Firma <a href="Xilinx" title="Xilinx">Xilinx</a> zur Fehlerkorrektur mittels Hamming-Codes<a href="#cite_note-2">[2]</a> wird von einem erweiterten Hamming-Code mit den Parametern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (128,120)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (128,120)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6faec60693423c363194cb0cfc67211c420d33e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.818ex; height:2.843ex;" alt="{\displaystyle (128,120)}" loading="lazy"> als Basis ausgegangen. Daraus wird ein verkürzter Hamming-Code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (72,64)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (72,64)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/280775dc89191aeeddc1867744955391c0a495c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.493ex; height:2.843ex;" alt="{\displaystyle (72,64)}" loading="lazy"> gebildet, dessen Codewortlänge exakt der Datenbusbreite des DRAM-Speichermoduls entspricht und 64 Nutzdatenbits pro Adresse speichern kann. Dabei werden alle Paritätsbits des <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (128,120)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (128,120)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6faec60693423c363194cb0cfc67211c420d33e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.818ex; height:2.843ex;" alt="{\displaystyle (128,120)}" loading="lazy"> Hamming-Codes in das auf 72 Stellen verkürzte Codewort übernommen. Die Datenbitstellen 65 bis 120 sind immer auf logisch-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> gesetzt und werden nicht gespeichert.

<div class="mw-heading mw-heading2"><h2 id="Weitere_Zahlensysteme">Weitere Zahlensysteme</h2></div>

Bei dem im Artikel vorgestellten binären Hamming-Code gibt es nur zwei mögliche Zustände pro Stelle des Datenwortes oder Codewortes (genau das bedeutet „binär“). In der <a href="Zahlentheorie" title="Zahlentheorie">Zahlentheorie</a> wird dieser Umstand mittels <a href="Galois-K%C3%B6rper" class="mw-redirect" title="Galois-Körper">Galois-Körpern</a> der Charakteristik zwei, abgekürzt GF(2), ausgedrückt. Besondere Eigenschaft aller binärer, fehlerkorrigierender Codes ist, dass bereits die Ermittlung der Fehlerposition zur Fehlerkorrektur ausreicht: Da nur zwei mögliche Zustände pro Stelle existieren, kann ein Fehler mit ermittelter Position immer durch Inversion (0 ↔ 1) der betreffenden Stelle korrigiert werden.

Neben den binären Hamming-Code gibt es auch Verallgemeinerungen auf weitere, höhere <a href="Zahlensystem" title="Zahlensystem">Zahlensysteme</a> wie beispielsweise den <a href="Tern%C3%A4rsystem" title="Ternärsystem">ternären</a> Hamming-Code in GF(3). Der ternäre Hamming-Code weist pro Stelle drei Zustände auf: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\{0,1,2\right\}}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{0,1,2\right\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/775427951303731b38c6cbf034a2892263fbd11c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.88ex; height:2.843ex;" alt="{\displaystyle \left\{0,1,2\right\}}" loading="lazy">. Zur Fehlerkorrektur ist bei allen nicht-binären Codes, neben der Lokalisierung der Fehlerposition, auch eine zusätzliche Information nötig, auf welche der anderen Möglichkeiten eine bestimmte Stelle geändert werden muss.

Allgemein lassen sich auch Hamming-Codes auf Galois-Körpern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle GF(q)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle GF(q)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7632e02672649089c63c998757aa3afc0782a0f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.446ex; height:2.843ex;" alt="{\displaystyle GF(q)}" loading="lazy"> bilden, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> eine <a href="Primzahl" title="Primzahl">Primzahlpotenz</a> sein muss, d. h. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q=p^{s}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=p^{s}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f93b8b013966f560794963fc69df035698a8f254.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.341ex; height:2.676ex;" alt="{\displaystyle q=p^{s}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\in \{2,3,5,7,\ldots \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\in \{2,3,5,7,\ldots \}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e06c2a668a67b27f7ff6630a8392f3d4a3058135.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:17.933ex; height:2.843ex;" alt="{\displaystyle p\in \{2,3,5,7,\ldots \}}" loading="lazy"> eine Primzahl und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fde27eac1945df21b2ef2f5a15859e4e9c288698.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.609ex; height:2.176ex;" alt="{\displaystyle s\in \mathbb {N} }" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Vereinfachte_Variation_mit_Beispiel">Vereinfachte Variation mit Beispiel</h2></div>

Eine starke Vereinfachung bietet die folgende Hamming-Code-Variante, hier werden die benötigten Hamming-Bits einfach angehängt, auch entfällt das Umdrehen der Binärzahl.

Beispiel Übertragung:

Dezimalzahl 86 (gespeichert in 8 Bits) soll übertragen werden.

86 = 01010110

→ Hamming-Bits werden benötigt.

01010110 hat 1er Bits an den Stellen (von rechts gezählt): 2, 3, 5 und 7

Aufschreiben der Stellen der 1er Bits binär untereinander und mit Parität ergänzen. D.h. jede Spalte muss eine gerade Anzahl an 1er Bits haben.

0010 (= 2. Stelle)

0011 (= 3. Stelle)

0101 (= 5. Stelle)

0111 (= 7. Stelle)

......

0011 (ergänzt, so dass in jeder Spalte eine gerade Anzahl 1er ist)

Übertragene Daten mit Hamming-Code:

01010110|0011

Binärzahl|Hamming-Bits

Beispiel Fehlersuche:

Empfangen wurde 01000110|0011

Hamming-Code neu berechnen:

01000110 hat 1er an Stellen: 2,3,7

0010 (= 2. Stelle)

0011 (= 3. Stelle)

0111 (= 7. Stelle)

0011 (= übertragener Hamming-Code)

......

0101 → da nicht 0000, sondern 0101 = 5 → 5. Bit falsch

01010110|0011 = 86 von oben [der Hamming-Code konnte den 1 Bit Fehler korrigieren]

Vergleich mit dem originalen Hamming-Code:

Beim ursprünglichen Hamming-Code funktioniert das Aufschreiben der Stellen zur Feststellung der Parität genauso, allerdings müssen die Bits vorher an die richtige Stelle gesetzt werden. Zum Beispiel von oben:

86 = 01010110 -> 0101?011?0?? (die ? stehen jeweils für das Hamming-Bit)

1er Bits haben wir an den Stellen: 5, 6, 9, 11

0101 (= 5. Stelle)

0110 (= 6. Stelle)

1001 (= 9. Stelle)

1011 (= 11. Stelle)

......

0001 (ergänzt, so dass in jeder Spalte eine gerade Anzahl 1er ist)

Hamming-Code original [ohne umdrehen der Bitfolge]:

010100110001

Die vereinfachte Variation hat allerdings eine Schwäche, die der originale Hamming Code nicht hat: Sie kann einen Fehler in den Datenbits nicht von einem Fehler in den Hamming-Code-Bits unterscheiden, vgl. die folgenden 2 Beispiele:

Beispiel Fehlersuche mit Fehler im 4. Datenbit:

Empfangen wurde 01011110|0011

Hamming-Code neu berechnen:

01011110 hat 1er an Stellen: 2,3,4,5,7

0010 (= 2. Stelle)

0011 (= 3. Stelle)

0100 (= 4. Stelle)

0101 (= 5. Stelle)

0111 (= 7. Stelle)

0011 (= übertragener Hamming-Code)

......

0100 → da nicht 0000, sondern 0100 = 4 → Hier wird das 4. Bit als falsch erkannt.

01010110|0011 = 86 von oben [der Hamming-Code konnte den 1 Bit Fehler korrigieren]

Beispiel Fehlersuche mit Fehler im 3. Hamming-Code-Bit:

Empfangen wurde 01010110|0111

Hamming-Code neu berechnen:

01010110 hat 1er an Stellen: 2,3,5,7

0010 (= 2. Stelle)

0011 (= 3. Stelle)

0101 (= 5. Stelle)

0111 (= 7. Stelle)

0111 (= übertragener Hamming-Code)

......

0100 → da nicht 0000, sondern 0100 = 4 → 4. Hier erkennt der Algorithmus ebenfalls einen Fehler im 4. Datenbit.

01011110|0111 = 94 Die Anwendung des Korrekturalgorithmus führt hier zu einem Fehler im Datenbit an Stelle zu einer Korrektur des Hamming-Code-Bits.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Martin_Bossert" title="Martin Bossert">Martin Bossert</a>: <cite style="font-style:italic">Kanalcodierung</cite>. 2. vollständig neubearbeitete und erweiterte Auflage. Teubner, Stuttgart 1998, ISBN 3-519-16143-5 (Informationstechnik).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Hamming-Code&rft.au=Martin+Bossert&rft.btitle=Kanalcodierung&rft.date=1998&rft.edition=2.+vollst%C3%A4ndig+neubearbeitete+und+erweiterte&rft.genre=book&rft.isbn=3519161435&rft.place=Stuttgart&rft.pub=Teubner" style="display:none"> </li>

<li>Todd K. Moon: <cite style="font-style:italic">Error Correction Coding. Mathematical Methods and Algorithms</cite>. John Wiley & Sons, Hoboken NJ 2005, ISBN 0-471-64800-0.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Hamming-Code&rft.au=Todd+K.+Moon&rft.btitle=Error+Correction+Coding.+Mathematical+Methods+and+Algorithms&rft.date=2005&rft.genre=book&rft.isbn=0471648000&rft.place=Hoboken+NJ&rft.pub=John+Wiley+%26+Sons" style="display:none"> </li>

<li>André Neubauer: <cite style="font-style:italic">Kanalcodierung. Eine Einführung für Ingenieure, Informatiker und Naturwissenschaftler</cite>. J.Schlembach Fachverlag, Wilburgstetten 2006, ISBN 3-935340-51-6.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Hamming-Code&rft.au=Andr%C3%A9+Neubauer&rft.btitle=Kanalcodierung.+Eine+Einf%C3%BChrung+f%C3%BCr+Ingenieure%2C+Informatiker+und+Naturwissenschaftler&rft.date=2006&rft.genre=book&rft.isbn=3935340516&rft.place=Wilburgstetten&rft.pub=J.Schlembach+Fachverlag" style="display:none"> </li>

<li><a href="Hermann_Rohling" title="Hermann Rohling">Hermann Rohling</a>: <cite style="font-style:italic">Einführung in die Informations- und Codierungstheorie</cite>. Teubner, Stuttgart 1995, ISBN 3-519-06174-0 (Teubner Studienbücher – Elektrotechnik).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Hamming-Code&rft.au=Hermann+Rohling&rft.btitle=Einf%C3%BChrung+in+die+Informations-+und+Codierungstheorie&rft.date=1995&rft.genre=book&rft.isbn=3519061740&rft.place=Stuttgart&rft.pub=Teubner" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a class="external text" href="https://commons.wikimedia.org/wiki/Hamming_codes?uselang=de">Commons: Hamming codes</a> – Album mit Bildern, Videos und Audiodateien</div>

<ul><li><a rel="nofollow" class="external text" href="http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl">Hamming-Code-Tool</a></li>

<li><a rel="nofollow" class="external text" href="http://ti.itec.uka.de/Visualisierungen/HammingCode/">Java-Applet zur Visualisierung</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> <a rel="nofollow" class="external text" href="https://calhoun.nps.edu/bitstream/handle/10945/64206/Hamming_error_dect_and_error_correct_codes.pdf">Richard W. Hamming: Error Detection and Error Correction Codes</a>. In: The Bell System Technical Journal, Vol. XXIX 2, 1950, Seite 147–160.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> <a rel="nofollow" class="external text" href="http://www.xilinx.com/support/documentation/application_notes/xapp645.pdf">Fehlererkennung mittels verkürztem Hamming-Code.</a> (PDF; 184 kB) Firmenschrift (englisch)

</li>

</ol>

</div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-09-15" href="https://de.wikipedia.org/wiki/?title=Hamming-Code&oldid=259756848">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>